<!DOCTYPE html>
<html lang="en">





<head>
  <meta charset="UTF-8">
  <link rel="apple-touch-icon" sizes="76x76" href="/img/apple-touch-icon.png">
  <link rel="icon" type="image/png" href="https://img.fungnotl.cn/basket.png">
  <meta name="viewport"
        content="width=device-width, initial-scale=1.0, maximum-scale=1.0, user-scalable=no, shrink-to-fit=no">
  <meta http-equiv="x-ua-compatible" content="ie=edge">
  <meta name="description" content="">
  <meta name="author" content="John Doe">
  <meta name="keywords" content="">
  <title>ArrayList动态扩容及其验证(JDK12源码分析) ~ fungnotl的博客</title>

  <link rel="stylesheet" href="/lib/font-awesome/css/all.min.css"  >
<link rel="stylesheet" href="/lib/bootstrap/css/bootstrap.min.css"  >
<link rel="stylesheet" href="/lib/mdbootstrap/css/mdb.min.css"  >
<link rel="stylesheet" href="/lib/github-markdown/github-markdown.min.css"  >
<link rel="stylesheet" href="//at.alicdn.com/t/font_1067060_qzomjdt8bmp.css">


  <link rel="stylesheet" href="/lib/prettify/tomorrow-night-eighties.min.css"  >

<link rel="stylesheet" href="/css/main.css"  >


  <link rel="stylesheet" href="/lib/fancybox/jquery.fancybox.min.css"  >


</head>


<body>
  <header style="height: 70vh;">
    <nav id="navbar" class="navbar fixed-top  navbar-expand-lg navbar-dark scrolling-navbar">
  <div class="container">
    <a class="navbar-brand"
       href="/">&nbsp;<strong>fungnotl的博客</strong>&nbsp;</a>

    <button id="navbar-toggler-btn" class="navbar-toggler" type="button" data-toggle="collapse"
            data-target="#navbarSupportedContent"
            aria-controls="navbarSupportedContent" aria-expanded="false" aria-label="Toggle navigation">
      <div class="animated-icon"><span></span><span></span><span></span></div>
    </button>

    <!-- Collapsible content -->
    <div class="collapse navbar-collapse" id="navbarSupportedContent">
      <ul class="navbar-nav ml-auto text-center">
        
          
          
          <li class="nav-item">
            <a class="nav-link" href="/">主页</a>
          </li>
        
          
          
          <li class="nav-item">
            <a class="nav-link" href="/archives/">归档</a>
          </li>
        
          
          
          <li class="nav-item">
            <a class="nav-link" href="/tags/">标签</a>
          </li>
        
          
          
          <li class="nav-item">
            <a class="nav-link" href="/about/">我</a>
          </li>
        
        
          <li class="nav-item" id="search-btn">
            <a class="nav-link" data-toggle="modal" data-target="#modalSearch">&nbsp;&nbsp;<i
                class="iconfont icon-search"></i>&nbsp;&nbsp;</a>
          </li>
        
      </ul>
    </div>
  </div>


</nav>

    <div class="view intro-2" id="background"
         style="background: url('https://fungnotl-img.oss-cn-hangzhou.aliyuncs.com/index.jpg')no-repeat center center;
           background-size: cover;
           background-attachment: fixed;">
      <div class="full-bg-img">
        <div class="mask rgba-black-light flex-center">
          <div class="container text-center white-text fadeInUp">
            <span class="h2" id="subtitle">
              
            </span>

            
              <br>
              
                <p class="mt-3">
                  <i class="fas fa-calendar-alt" aria-hidden="true"></i>&nbsp;
                  Wednesday, January 1st 2020, 12:00 am
                </p>
              

              <p>
                
                  
                  &nbsp;<i class="far fa-chart-bar"></i>
                  <span class="post-count">
                    1.5k 字
                  </span>&nbsp;
                

                
                  
                  &nbsp;<i class="far fa-clock"></i>
                  <span class="post-count">
                      7 分钟
                  </span>&nbsp;
                

                
                  <!-- 不蒜子统计文章PV -->
                  
                  &nbsp;<i class="far fa-eye" aria-hidden="true"></i>&nbsp;
                  <span id="busuanzi_container_page_pv">
                    <span id="busuanzi_value_page_pv"></span> 次
                  </span>&nbsp;
                
              </p>
            
          </div>

          
        </div>
      </div>
    </div>
  </header>

  <main>
    
      

<div class="container-fluid">
  <div class="row">
    <div class="d-none d-lg-block col-lg-2"></div>
    <div class="col-lg-8 nopadding-md">
      <div class="py-5 z-depth-3" id="board">
        <div class="post-content mx-auto" id="post">
          <div class="markdown-body">
            <h1 id="ArrayList动态扩容-JDK12"><a href="#ArrayList动态扩容-JDK12" class="headerlink" title="ArrayList动态扩容(JDK12)"></a>ArrayList动态扩容(JDK12)</h1><p>最近有在温习一下java容器,今天就开始读一下ArrayList的动态扩容</p>
<h2 id="ArrayList是什么"><a href="#ArrayList是什么" class="headerlink" title="ArrayList是什么?"></a>ArrayList是什么?</h2><blockquote>
<p>ArrayList叫做动态数组,实现了长度可变的数组, 在内存中分配连续的空间.</p>
</blockquote>
<p><strong>优缺点</strong></p>
<blockquote>
<p>优点:<br>遍历元素和随机访问元素的效率较高<br>缺点:<br>添加和删除需要大量移动元素,效率低;按照内容查询效率低;</p>
</blockquote>
<hr>
<p>ArrayList是在object包中,继承于Collection与其子类AbstractList的.</p>
<p>所有<strong>实现了的接口</strong>有:Serializable(序列化), Cloneable(克隆), Iratable(迭代器),Collection(集合), List(列表),RandomAccess(随机存取)<br><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9mdW5nbm90bC1pbWcub3NzLWNuLWhhbmd6aG91LmFsaXl1bmNzLmNvbS9BcnJheUxpc3QlRTUlOEElQTglRTYlODAlODElRTYlODklQTklRTUlQUUlQjkvYXJyYXlsaXN0XzEuanBn?x-oss-process=image/format,png" srcset="/img/loading.gif" alt="ArrayList继承关系"></p>
<h2 id="动态扩容"><a href="#动态扩容" class="headerlink" title="动态扩容"></a>动态扩容</h2><h3 id="初始化"><a href="#初始化" class="headerlink" title="初始化:"></a>初始化:</h3><p><strong>三个初始化方法:</strong></p>
<ul>
<li>默认构造器</li>
</ul>
<pre><code class="java">/**
     * Constructs an empty list with an initial capacity of ten.
     * (构造一个初始容量为10的空列表)
     */
    public ArrayList() {
        this.elementData = DEFAULTCAPACITY_EMPTY_ELEMENTDATA;
    }</code></pre>
<pre><code class="java">/**
     * Shared empty array instance used for default sized empty instances. We
     * distinguish this from EMPTY_ELEMENTDATA to know how much to inflate when
     * first element is added.
     *(为默认空实例提供的空的数组实例,用来区分EMPTY_ELEMENTDATA,以便了解当添加第一个元素时是如何扩容的)
     */
     //简而言之就是个空数组
    private static final Object[] DEFAULTCAPACITY_EMPTY_ELEMENTDATA = {};</code></pre>
<ul>
<li>用指定的大小来初始化内部的数组</li>
</ul>
<pre><code class="java">/**
     * Constructs an empty list with the specified initial capacity.
     *(用指定的初始容量构造一个空的列表)
     * @param  initialCapacity  the initial capacity of the list
     * @throws IllegalArgumentException if the specified initial capacity
     *         is negative
     */
    public ArrayList(int initialCapacity) {
        if (initialCapacity &gt; 0) {
            this.elementData = new Object[initialCapacity];
        } else if (initialCapacity == 0) {
            this.elementData = EMPTY_ELEMENTDATA;
        } else {
            throw new IllegalArgumentException(&quot;Illegal Capacity: &quot;+
                                               initialCapacity);
        }
    }</code></pre>
<ul>
<li>用一个ICollection对象来构造，并将该集合的元素添加到ArrayList</li>
</ul>
<pre><code class="java">/**
     * Constructs a list containing the elements of the specified
     * collection, in the order they are returned by the collection&#39;s
     * iterator.
     * (构造一个包含了该集合的列表,并按照集合的迭代器依次返回)
     * @param c the collection whose elements are to be placed into this list
     * @throws NullPointerException if the specified collection is null
     */
    public ArrayList(Collection&lt;? extends E&gt; c) {
        //将集合C中的内容转化为数组形式存放
        elementData = c.toArray();
        if ((size = elementData.length) != 0) {
            // defend against c.toArray (incorrectly) not returning Object[]
            // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
        } else {
            // replace with empty array.
            this.elementData = EMPTY_ELEMENTDATA;
        }
    }</code></pre>
<blockquote>
<p><strong>这里这一段可能不易理解</strong></p>
<pre><code class="java">            // defend against c.toArray (incorrectly) not returning Object[]
            // (see e.g. https://bugs.openjdk.java.net/browse/JDK-6260652)
            //elementData的对象不等于toArray()方法的运行时对象,保证了这个,再进行拷贝
            //否则数组有可能发生错乱
            if (elementData.getClass() != Object[].class)
                elementData = Arrays.copyOf(elementData, size, Object[].class);
-----------------------------------------------------------------------------------------------------------------------------------
        /**      toArray()方法
        //简而言之意思就是:返回一个数组,这个数组是按照之前的顺序返回得到的
     * Returns an array containing all of the elements in this collection.
     * If this collection makes any guarantees as to what order its elements
     * are returned by its iterator, this method must return the elements in
     * the same order. The returned array&#39;s {@linkplain Class#getComponentType
     * runtime component type} is {@code Object}.
     *

     //返回一个运行时组件类型为对象的数组,包含所有该集合中的元素
     * @return an array, whose {@linkplain Class#getComponentType runtime component
     * type} is {@code Object}, containing all of the elements in this collection
     */
    Object[] toArray();</code></pre>
</blockquote>
<h2 id="容量的变化"><a href="#容量的变化" class="headerlink" title="容量的变化"></a>容量的变化</h2><p>容量的变化是先从创建开始的,然后添加元素,伴随着容量的变化;</p>
<h3 id="元素的添加"><a href="#元素的添加" class="headerlink" title="元素的添加"></a>元素的添加</h3><pre><code class="java"> /**
     * This helper method split out from add(E) to keep method
     * bytecode size under 35 (the -XX:MaxInlineSize default value),
     * which helps when add(E) is called in a C1-compiled loop.
     *(这个辅助方法是从add(E)方法分离而来的,为了保持方法字节码低于35,这将有助于add(E)方法调用C1编译循环)(至于咋优化的咱也不想知道)
     */
    private void add(E e, Object[] elementData, int s) {
        if (s == elementData.length)
            elementData = grow();
        elementData[s] = e;
        size = s + 1;
    }

    /**
     * Appends the specified element to the end of this list.
     *(追加指定的元素到列表的末端)
     * @param e element to be appended to this list
     * @return {@code true} (as specified by {@link Collection#add})
     */
    public boolean add(E e) {
        modCount++;
        //此处调用上面的那个方法
        add(e, elementData, size);
        return true;
    }</code></pre>
<h3 id="元素的扩容"><a href="#元素的扩容" class="headerlink" title="元素的扩容"></a>元素的扩容</h3><pre><code class="java">/**
     * Increases the capacity to ensure that it can hold at least the
     * number of elements specified by the minimum capacity argument.
     *(增加容量来保证至少能够容纳这些元素)
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private Object[] grow(int minCapacity) {
        return elementData = Arrays.copyOf(elementData,
                                           newCapacity(minCapacity));
    }

    private Object[] grow() {
        return grow(size + 1);
    }

    /**
     * Returns a capacity at least as large as the given minimum capacity.
     * Returns the current capacity increased by 50% if that suffices.
     * Will not return a capacity greater than MAX_ARRAY_SIZE unless
     * the given minimum capacity is greater than MAX_ARRAY_SIZE.
     *(返回一个至少与给定的最小容量一样大的容量)
     *(如果足够的话,返回增加当前容量增加50%的容量)
     *(除非给定的(传参传进来的)最小容量比MAX_ARRAY_SIZE的值要大,不然不会返回一个比MAX_ARRAY_SIZE还大的值)
     * @param minCapacity the desired minimum capacity
     * @throws OutOfMemoryError if minCapacity is less than zero
     */
    private int newCapacity(int minCapacity) {
        // overflow-conscious code
        int oldCapacity = elementData.length;
        //(oldCapacity &gt;&gt; 1)右移操作,右移一位,二进制数右移一位,左边补0;相当于除以二;
        int newCapacity = oldCapacity + (oldCapacity &gt;&gt; 1);
        if (newCapacity - minCapacity &lt;= 0) {
            if (elementData == DEFAULTCAPACITY_EMPTY_ELEMENTDATA)
                return Math.max(DEFAULT_CAPACITY, minCapacity);
            if (minCapacity &lt; 0) // overflow
                throw new OutOfMemoryError();
            return minCapacity;
        }
        //三元运算符,(判断表达式)? A : B;加入判断表达式得出为true,则返回A,否则返回B
        return (newCapacity - MAX_ARRAY_SIZE &lt;= 0)
            ? newCapacity
            : hugeCapacity(minCapacity);
    }</code></pre>
<p><strong>再贴出hugeCapacity()方法</strong></p>
<pre><code class="java">//无需多言,相信大家都看的懂
 private static int hugeCapacity(int minCapacity) {
        if (minCapacity &lt; 0) // overflow
            throw new OutOfMemoryError();
        return (minCapacity &gt; MAX_ARRAY_SIZE)
            ? Integer.MAX_VALUE
            : MAX_ARRAY_SIZE;
    }</code></pre>
<h2 id="调试并总结"><a href="#调试并总结" class="headerlink" title="调试并总结"></a>调试并总结</h2><h3 id="调试代码"><a href="#调试代码" class="headerlink" title="调试代码"></a>调试代码</h3><p>仍然贴代码</p>
<pre><code class="java">public class test {
    public static void main(String[] args) {
        ArrayList arrayList = new ArrayList();
        System.out.println(getArrayListCapacity(arrayList));
        for (int i = 0; i &lt; 5; i++) {
            arrayList.add(i);
            for (int j = 0; j &lt; 5; j++) {
                arrayList.add(j);
                //想看到更多的容量值变换,可以将i,j的值变大,并在循环体打印
                // System.out.println(getArrayListCapacity(arrayList));
            }
            System.out.println(getArrayListCapacity(arrayList));
        }

    }

    //利用反射机制获取当前ArrayList对象的容量
    public static int getArrayListCapacity(ArrayList arrayList) {
        Class&lt;ArrayList&gt; arrayListClass = ArrayList.class;
        try {
            Field field = arrayListClass.getDeclaredField(&quot;elementData&quot;);
            field.setAccessible(true);
            Object[] objects = (Object[])field.get(arrayList);
            return objects.length;
        } catch (NoSuchFieldException e) {
            e.printStackTrace();
            return -1;
        } catch (IllegalAccessException e) {
            e.printStackTrace();
            return -1;
        }
    }
}</code></pre>
<blockquote>
<p>输出内容</p>
</blockquote>
<p><img src="https://imgconvert.csdnimg.cn/aHR0cHM6Ly9mdW5nbm90bC1pbWcub3NzLWNuLWhhbmd6aG91LmFsaXl1bmNzLmNvbS9BcnJheUxpc3QlRTUlOEElQTglRTYlODAlODElRTYlODklQTklRTUlQUUlQjkvb3V0UHV0LmpwZw?x-oss-process=image/format,png" srcset="/img/loading.gif" alt="在这里插入图片描述"></p>
<h3 id="总结"><a href="#总结" class="headerlink" title="总结"></a>总结</h3><p>结果也是十分清晰:<br>创建时为0,然后马上给了10的容量值,当容量到达了10后,再次添加到10的1.5倍,一直如此,这就是ArrayList的动态扩容了.</p>

            <hr>
          </div>
          <br>
          <div>
            <p>
            
            
              <span>
                <i class="iconfont icon-tag"></i>
                
                  <a class="hover-with-bg" href="/tags/ArrayList">ArrayList</a>
                
                  <a class="hover-with-bg" href="/tags/%E6%BA%90%E7%A0%81">源码</a>
                
              </span>
            
            </p>
            
              <p class="note note-warning">本博客所有文章除特别声明外，均采用 <a href="https://zh.wikipedia.org/wiki/Wikipedia:CC_BY-SA_3.0%E5%8D%8F%E8%AE%AE%E6%96%87%E6%9C%AC" target="_blank" rel="nofollow noopener noopener">CC BY-SA 3.0协议</a> 。转载请注明出处！</p>
            
          </div>
        </div>
      </div>
    </div>
    <div class="d-none d-lg-block col-lg-2 toc-container">
      
  <div id="toc">
    <p class="h4"><i class="far fa-list-alt"></i>&nbsp;TOC</p>
    <div id="tocbot"></div>
  </div>

    </div>
  </div>
</div>

<!-- custom -->


<!-- Comments -->
<div class="col-lg-7 mx-auto nopadding-md">
  <div class="container comments mx-auto" id="comments">
    
      <br><br>
      
      
   <!-- 来必力City版安装代码 -->
<div id="lv-container" data-id="city" data-uid="MTAyMC80Nzg4My8yNDM4MA==">
	<script type="text/javascript">
   (function(d, s) {
       var j, e = d.getElementsByTagName(s)[0];

       if (typeof LivereTower === 'function') { return; }

       j = d.createElement(s);
       j.src = 'https://cdn-city.livere.com/js/embed.dist.js';
       j.async = true;

       e.parentNode.insertBefore(j, e);
   })(document, 'script');
	</script>
<noscript> 为正常使用来必力评论功能请激活JavaScript</noscript>
</div>
<!-- City版安装代码已完成 -->
  
  
    
  </div>
</div>

    
  </main>

  
    <a class="z-depth-1" id="scroll-top-button" href="#" role="button">
      <i class="fa fa-chevron-up scroll-top-arrow" aria-hidden="true"></i>
    </a>
  

  
    <div class="modal fade" id="modalSearch" tabindex="-1" role="dialog" aria-labelledby="ModalLabel"
     aria-hidden="true">
  <div class="modal-dialog modal-dialog-scrollable modal-lg" role="document">
    <div class="modal-content">
      <div class="modal-header text-center">
        <h4 class="modal-title w-100 font-weight-bold">Search</h4>
        <button type="button" id="local-search-close" class="close" data-dismiss="modal" aria-label="Close">
          <span aria-hidden="true">&times;</span>
        </button>
      </div>
      <div class="modal-body mx-3">
        <div class="md-form mb-5">
          <input type="text" id="local-search-input" class="form-control validate">
          <label data-error="x" data-success="v"
                 for="local-search-input">keyword</label>
        </div>
        <div class="list-group" id="local-search-result"></div>
      </div>
    </div>
  </div>
</div>
  

  <footer class="mt-5">
  <div class="text-center py-3">
    <a href="https://hexo.io" target="_blank" rel="nofollow noopener"><b>Hexo</b></a>
    <i class="iconfont icon-love"></i>
    <a href="https://github.com/fluid-dev/hexo-theme-fluid" target="_blank" rel="nofollow noopener"> <b>Fluid</b></a>
    <br>

    
  
    <!-- 不蒜子统计PV -->
    
    &nbsp;<span id="busuanzi_container_site_pv">总访问量 
          <span id="busuanzi_value_site_pv"></span> 次</span>&nbsp;
  
  
    <!-- 不蒜子统计UV -->
    
    &nbsp;<span id="busuanzi_container_site_uv">总访客数 
            <span id="busuanzi_value_site_uv"></span> 人</span>&nbsp;
  
  <br>



    
  <!-- 备案信息 -->
  <a href="http://beian.miit.gov.cn/" target="_blank"
     rel="nofollow noopener">浙ICP备19040843号</a>
  


  </div>
</footer>

<!-- SCRIPTS -->
<script src="/lib/jquery/jquery.min.js" ></script>
<script src="/lib/popper/popper.min.js" ></script>
<script src="/lib/bootstrap/js/bootstrap.min.js" ></script>
<script src="/lib/mdbootstrap/js/mdb.min.js" ></script>
<script src="/js/main.js" ></script>


  <script src="/js/lazyload.js" ></script>



  
    <script src="/lib/tocbot/tocbot.min.js" ></script>
  
  <script src="/js/post.js" ></script>



  <script src="/lib/smooth-scroll/smooth-scroll.min.js" ></script>



  <script async src="//busuanzi.ibruce.info/busuanzi/2.3/busuanzi.pure.mini.js" ></script>


<!-- Plugins -->


  

  

  

  

  




  <script src="/lib/prettify/prettify.min.js" ></script>
  <script>
    $(document).ready(function () {
      $('pre').addClass('prettyprint  linenums');
      prettyPrint();
    })
  </script>



  <script src="/lib/typed/typed.min.js" ></script>
  <script>
    var typed = new Typed('#subtitle', {
      strings: [
        '  ',
        "ArrayList动态扩容及其验证(JDK12源码分析)&nbsp;",
      ],
      cursorChar: "_",
      typeSpeed: 50,
      loop: false,
    });
    typed.stop();
    $(document).ready(function () {
      $(".typed-cursor").addClass("h2");
      typed.start();
    });
  </script>



  <script src="/lib/anchor/anchor.min.js" ></script>
  <script>
    anchors.options = {
      placement: "right",
      visible: "false",
      
    };
    var el = "h1,h2,h3,h4,h5,h6".split(",");
    var res = [];
    for (item of el) {
      res.push(".markdown-body > " + item)
    }
    anchors.add(res.join(", "))
  </script>



  <script src="/js/local-search.js" ></script>
  <script>
    var path = "/local-search.xml";
    var inputArea = document.querySelector("#local-search-input");
    inputArea.onclick = function () {
      getSearchFile(path);
      this.onclick = null
    }
  </script>



  <script src="/lib/fancybox/jquery.fancybox.min.js" ></script>
  <script>
    $("#post img:not(.no-zoom img, img[no-zoom])").each(
      function () {
        var element = document.createElement("a");
        $(element).attr("data-fancybox", "images");
        $(element).attr("href", $(this).attr("src"));
        $(this).wrap(element);
      }
    );
  </script>





  





</body>
</html>
